#include "GeneticSolver.hpp"
#include "BasicSolver.hpp"
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include "NiceMergeSolver.hpp"
#include "VNDTry.hpp"

/*
 * 	Pour le veritable algo genetique et le cross :
 * 		on prend une tournee pourrie d'une sol A et une tournee bien d'une sol B
 * 		il faut qu'elles aient au moins 1 client en commun
 * 		on extrait la liste des clients
 * 		on balance tout dans le merger
 * 		=> on obtiendra alors plusieurs tournees, et avec du bol deux, et beaucoup de bol une seule
 * 
 * 	Pour ameliorer le merger, penser eventuellement a creer une tri-subsol
 * 	au lieu d'une bi-subsol. Et alterner dans le merger entre tri et bi subsol.
 * 	// il faut pour cela essayer de coder un or-opt entre trois tournees
 * 	// et un 2-opt entre trois tournees
 */


void	GeneticSolver::cross_over(	Tournee& in1, Tournee& in2, Solution& inSon) EXC_THROWER()
{
	EXC_RETHROW_BEGIN()
	{
		std::map<unsigned, unsigned>	clients;
		std::map<unsigned, unsigned>	doublons;
		std::map<unsigned, unsigned>::iterator	it;
		// creer une solution vide
		Solution	sol(soVRPTW);
		Solution 	bestsol(soVRPTW);
		SolutionEval	bestsoleval;
		SolutionEval	soleval;
		// verifier les doublons de clients dans les tournees
		unsigned	client = DEPOT;
		unsigned	nclient = 0xdeb1e;
		unsigned	i = 0;
		unsigned	d = 99;
		unsigned	n_tournee1;
		unsigned	n_tournee2;
		
		i = 0;
		
		if ((in1.getNbClients() == 0) && (in2.getNbClients() == 0))
			return;
		
		for (;;)
		{
			nclient = in1.getSuccessorOf(client);
			
			if (nclient == DEPOT)
				break;
			
			if (soVRPTW.isRDepot(nclient))
			{
				sol[i].insertClient(Tournee::INSERT_END, nclient);
				sol.validateTournee(i);
				client = nclient;
				continue;
			}
			
			if (inSon.hasClient(nclient))
			{
			}
			else
			{
				
				// specifier
				clients[nclient] = i;
				sol[i].insertClient(Tournee::INSERT_END, nclient);
				sol.validateTournee(i);
			}
			
			//std::cout << inSon.toString() << std::endl;
			//std::cout << sol.toString() << std::endl;
			client = nclient;
		}
		
		client = DEPOT;
		nclient = 0xdeb1e;
		i++;
		
		for (;;)
		{
			nclient = in2.getSuccessorOf(client);
			if (nclient == DEPOT)
				break;
			
			if (soVRPTW.isRDepot(nclient))
			{
				sol[i].insertClient(Tournee::INSERT_END, nclient);
				sol.validateTournee(i);
				client = nclient;
				continue;
			}
			
			// si client non affecte
			if ((it = clients.find(nclient)) != clients.end())
			{
				// RAND OU NB_CLIENTS ??
				// --> on garde les tailles de tournees ou non ??
				sol[it->second].erase(nclient);
				sol.validateTournee(it->second);
				i++;
				sol[i].insertClient(Tournee::INSERT_END, nclient);
				clients[nclient] = i;
				sol.validateTournee(i);
			}
			else if (inSon.hasClient(nclient))
			{
			}
			else
			{
				// specifier
				clients[nclient] = i;
				sol[i].insertClient(Tournee::INSERT_END, nclient);
				sol.validateTournee(i);				
			}
			
			//std::cout << sol.toString() << std::endl;
			client = nclient;
		}
		i++;
		
		bestsol = sol;
		sol.eval(&bestsoleval);
		
		unsigned	iteration = 0;
		unsigned	amelioration_iteration = 0;
		
		for (;; iteration++)
		{
			if ((iteration - amelioration_iteration) > 10)
				break;
			
			//std::cout << "loop get empty" << std::endl;
			for (unsigned k = 0 ; k < i ; k++)
			{
				localVND(sol[k], sol[(k + 1) % i], 4);
				sol.validateTournee(k);
				sol.validateTournee((k + 1) % i);
				sol.reorganize();
			}
			
			sol.eval(&soleval);
			if (soleval < bestsoleval)
			{
				amelioration_iteration = iteration;
				bestsoleval = soleval;
				bestsol = sol;
			}
		}
		
		bestsol.reorganize();
		for (unsigned i = 0 ; i < bestsoleval.seNTournees ; i++)
		{
			n_tournee1 = inSon.getEmptyRandomTournee();
			inSon[n_tournee1].append(sol[i]);
			inSon.validateTournee(n_tournee1);
		}
	}
	EXC_RETHROW_END()
}

/*
void		GeneticSolver::cross_over(	Tournee& in1, Tournee& in2, Solution& inSon) EXC_THROWER()
{
	EXC_RETHROW_BEGIN()
	{
		Solution	s(soVRPTW);
		
		
	}
	EXC_RETHROW_END()
}
*/

void		GeneticSolver::init()
{
	EXC_RETHROW_BEGIN()
	{
		std::deque<unsigned>	base;
		
		for (unsigned i = 0 ; i < soVRPTW.size() ; i++)
			base.push_back(i);
		
		for (unsigned i = 0 ; i < gsPopulation.size() ; i++)
		{
			//random_shuffle(base.begin(), base.end());
			//std::cout << "nmsolver execute" << std::endl;
			NiceMergeSolver	nmsolver(soVRPTW, base, 1);
			nmsolver.execute();
			gsPopulation[i] = nmsolver.getBestSolution();
			//std::cout << "nvalue" << std::endl;
			//std::cout << gsPopulation[i].toString() << std::endl;
			//getchar();
		}
		
		for (unsigned i = 0 ; i < (gsPopulation.size() >> 1) ; i++)
		{
			gsFathers[i] = &gsPopulation[(i << 1)];
			gsSons[i] = &gsPopulation[(i << 1) + 1];
		}
	}
	EXC_RETHROW_END()
}

/*
 * 	Impossible avec le codage actuel d'ameliorer les solutions
 * 	par contre possibilite d'ameliorer les tournees
 * 	dans le cadre de l'algorithme genetique, il faudrait penser
 * 	en population de tournees, et ensuite piocher dans cette population
 * 	pour construire une solution, la ca peut etre super rapide, et la pop
 * 	peut etre immense
 */
void	GeneticSolver::execute() EXC_THROWER()
{
	EXC_RETHROW_BEGIN()
	{
		std::multimap<SolutionEval, unsigned>	evals;
		std::multimap<SolutionEval, unsigned>::iterator	it;
		std::multimap<SolutionEval, unsigned>::reverse_iterator ir;
		unsigned								iteration = 0;
		unsigned								amelioration = 0;
		Solution								record(soVRPTW);
		SolutionEval							record_eval;
		VNDTry									vnd(soVRPTW);
		
		record.complete();
		record.eval(&record_eval);
		
		// INITIALISATION
		this->init();
		
		evals.clear();
		for (unsigned i = 0 ; i < gsPopulation.size() ; i++)
		{
			std::pair<SolutionEval, unsigned>	p;
			
			/*for (unsigned j = 0 ; j < (soVRPTW.size() >> 1) ; j++)
			{
				Tournee&	t1 = gsPopulation[i].operator[](j << 1);
				Tournee&	t2 = gsPopulation[i].operator[](((j << 1) + 1));
				
				localVND2(t1, t2, 5);
				gsPopulation[i].validateTournee(j << 1);
				gsPopulation[i].validateTournee(((j << 1) + 1));
					
				//std::cout << "solution eval end" << std::endl;
			}*/
			
			gsPopulation[i].eval(&p.first);
			//std::cout << p.first.toString() << std::endl;
			p.second = i;
			evals.insert(p);
		}
		
		
		
		it = evals.begin();
		ir = evals.rbegin();

		for (unsigned i = 0 ; i < (gsPopulation.size() >> 2) ; i++, ++it, ++ir)
		{
			gsFathers[(i << 1)] = &gsPopulation[it->second];
			gsFathers[(i << 1) + 1] = &gsPopulation[ir->second];
		}
		
		for (unsigned i = 0 ; i < (gsPopulation.size() >> 2) ; i++, ++it, ++ir)
		{
			gsSons[(i << 1)] = &gsPopulation[it->second];
			gsSons[(i << 1) + 1] = &gsPopulation[ir->second];
		}
		
		
		for (;; iteration++)
		{
			// cross_over
			for (unsigned i = 0 ; i < (gsPopulation.size() >> 2) ; i++)
			{
				gsFathers[(i << 1)]->shuffle();
				gsFathers[(i << 1)]->reorganize();
				gsFathers[(i << 1) + 1]->shuffle();
				gsFathers[(i << 1) + 1]->reorganize();
				gsSons[(i << 1)]->clear();
				gsSons[(i << 1) + 1]->clear();
				
				for (unsigned k = 0 ; k < soVRPTW.size() ; k++)
				{
					Tournee&	t1 = gsFathers[(i << 1)]->operator[](k);
					Tournee&	t2 = gsFathers[(i << 1) + 1]->operator[](k);
					
					gsFathers[(i << 1)]->validateTournee(k);
					gsFathers[(i << 1) + 1]->validateTournee(k);
					
					//std::cout << t1.toString() << std::endl;
					//std::cout << t2.toString() << std::endl;
					
					this->cross_over(t1, t2, *(gsSons[(i << 1)]));
					

					
					//std::cout << gsSons[(i << 1)]->toString() << std::endl;
					//getchar();
					
					this->cross_over(t2, t1, *gsSons[(i << 1) + 1]);
					//std::cout << gsSons[(i << 1) + 1]->toString() << std::endl;
				}
				
				
				for (unsigned j = 0 ; j < (soVRPTW.size() >> 1) ; j++)
				{
					Tournee&	t1 = gsSons[i]->operator[](j << 1);
					Tournee&	t2 = gsSons[i]->operator[](((j << 1) + 1));
					
					localVND2(t1, t2, 1);
					gsSons[i]->validateTournee(j << 1);
					gsSons[i]->validateTournee(((j << 1) + 1));
						
					//std::cout << "solution eval end" << std::endl;
				}
				
			}
			
			//std::cout << "end cross_over" << std::endl;
			
			// evolution population globale
			evals.clear();
			for (unsigned i = 0 ; i < gsPopulation.size() ; i++)
			{
				std::pair<SolutionEval, unsigned>	p;
				
				std::cout << "execute vnd" << std::endl;
				vnd.execute(gsPopulation[i], 1);
				
				gsPopulation[i] = vnd.getBestSolution();
				gsPopulation[i].eval(&p.first);
				//std::cout << p.first.toString() << std::endl;
				p.second = i;
				evals.insert(p);
			}
			
			
			
			it = evals.begin();
			ir = evals.rbegin();
			
			//std::cout << gsPopulation[it->second].toString() << std::endl;
			
			if (it->first < record_eval)
			{
				record = gsPopulation[it->second];
				record_eval = it->first;
				std::cout << record.toString() << std::endl;
				std::cout << record_eval.toString() << std::endl;
				std::cout << "amelioration " << amelioration << "@" << iteration << std::endl;
				amelioration++;
			}
			
			for (; it != evals.end() ; ++it)
			{
				std::cout << it->first.toString() << std::endl;
			}
			getchar();
			it = evals.begin();
			
			for (unsigned i = 0 ; i < (gsPopulation.size() >> 2) ; i++, ++it, ++ir)
			{
				gsFathers[(i << 1)] = &gsPopulation[it->second];
				gsFathers[(i << 1) + 1] = &gsPopulation[ir->second];
			}
			
			for (unsigned i = 0 ; i < (gsPopulation.size() >> 2) ; i++, ++it, ++ir)
			{
				gsSons[(i << 1)] = &gsPopulation[it->second];
				gsSons[(i << 1) + 1] = &gsPopulation[ir->second];
			}
		}
	}
	EXC_RETHROW_END()
}
